/**
 * @author hzq
 * @description 最小堆
 * @date 2024-11-03
 */
class MinHeap {
  // 堆数组
  heap: number[] = []

  /**
   * 获取父节点的索引
   * @param index 当前节点索引
   * @returns
   */
  getParentIndex(index: number) {
    return (index - 1) >> 1
  }

  /**
   * 获取左子节点的索引
   * @param index 当前节点索引
   * @returns
   */
  getLeftIndex(index: number) {
    return index * 2 + 1
  }

  /**
   * 获取右子节点的索引
   * @param index 当前节点索引
   * @returns
   */
  getRightIndex(index: number) {
    return index * 2 + 2
  }

  /**
   * 交换两个节点的位置
   * @param index1
   * @param index2
   */
  swap(index1: number, index2: number) {
    ;[this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1]
    ]
  }

  /**
   * 获取堆顶元素
   * @returns 堆顶元素
   */
  peek() {
    return this.heap[0]
  }

  /**
   * 获取堆的大小
   */
  get size() {
    return this.heap.length
  }

  /**
   * 插入元素
   * @param value 插入的值
   */
  insert(value: number) {
    this.heap.push(value)
    this.shiftUp(this.size - 1)
  }

  /**
   * 弹出堆顶元素
   * @returns 堆顶元素
   */
  pop() {
    this.heap[0] = this.heap.pop()!
    this.shiftDown(0)
  }

  /**
   * 向上调整堆
   * @param index 当前节点索引
   * @returns
   */
  private shiftUp(index: number) {
    if (index === 0) return
    const parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }

  /**
   * 向下调整堆
   * @param index 当前节点索引
   */
  private shiftDown(index: number) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
    }
  }
}

export default MinHeap
